/*

中国大学MOOC-陈越、何钦铭-数据结构基础习题集


01-1. 最大子列和问题(20)


给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，
其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。
例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。
现要求你编写程序，计算给定整数序列的最大子列和。

输入格式：

输入第1行给出正整数 K (<= 100000)；第2行给出K个整数，其间以空格分隔。

输出格式：

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例：
6
-2 11 -4 13 -5 -2
输出样例：
20

--------------------------------------------------------------------------------

{ -2, 11, -4, 13, -5, -2 }
子序列:
{ -2 } -> -2
{ -2, 11 } -> 9
{ -2, 11, -4 } -> 5
{ -2, 11, -4, 13 } -> 18
{ -2, 11, -4, 13, -5 } -> 13
{ -2, 11, -4, 13, -5, -2 } -> 11

{ 11 } -> 11
{ 11, -4 } -> 7
{ 11, -4, 13 } -> 20
{ 11, -4, 13, -5 } -> 15
{ 11, -4, 13, -5, -2 } -> 13

{ -4 } -> -4
{ -4, 13 } -> 9
{ -4, 13, -5 } -> 4
{ -4, 13, -5, -2 } -> 2

{ 13 } -> 13
{ 13, -5 } -> 8
{ 13, -5, -2 } -> 6

{ -5 } -> -5
{ -5, -2 } -> -7

{ -2 } -> -2



一个奇怪的发现：
课堂上一般强调
int n;
scanf("%d", n);
int a[n];
是错误的，因为动态嘛，但是实际gcc是可以编译的，有人说这是c99的特性，
但我用-std=c89也一样可以编译啊


下面分两种情况，在centos 6(64 bit)上用gcc 4.4.7：
int n, int a[n];
scanf("%d", n);
for (i = 0; i < n; ++i)
	a[i] = i;

用-Wall -std=c89是能编译通过的，但是比如说我输入的n是1000，那么按程序，得到的
a[i]应该是0~999，但实际上只能输出0~56


和

int n;
scanf("%d", n);
int a[n];

同样用-Wall -std=c89是能编译通过的，而且结果是跟程序相符的。




*/

#include <stdio.h>


int
main(int argc, char *argv[])
{
	int i, j, sum, max, max_i, max_j;
	int k, negative;

	negative = 1;
	scanf("%d", &k);
	int num[k];

	for (i = 0; i < k; ++i) {
		scanf("%d", &num[i]);
		if (num[i] >= 0)
			negative = 0;
	}

	if (negative) {
		printf("0\n");
		return 0;
	}


	/* 效率: O(n^2) */
	max = num[0];
	max_i = max_j = 0;
	for (i = 0; i < k; ++i) {
		sum = 0;
		for (j = i; j < k; ++j) {
			sum += num[j];
			if (sum > max) {
				max = sum;
				max_i = i;
				max_j = j;
			}
		}
	}

	/*
	printf("max: i = %d, j = %d\n", max_i, max_j);
	for (i = max_i; i <= max_j; ++i)
		printf("%d ", num[i]);
	printf("\n");
	*/

	printf("%d\n", max);

	return 0;
}


/*
 * 算法2：分而治之
 * 把大问题分成小问题逐一解决，最后把结果合并。
 *
 * 1.把数组分成两半，递归解决左右两边的问题；
 * 2.递归解决左边的问题：得到最大子列和；
 * 3.递归解决右边得到右边最大的子列和；
 * 4.找出左右两边跨越边界的最大子列和；
 * 5.数组最大的子列和就是上面三个数中的一个；
 *
 * 效率：O(nlogn)
 */



/*
 * 算法3：在线处理
 *
 * 效率：O(n)
 */
int
max_subseq_sum(int a[], int n)
{
	int i, sum, max_sum;
	sum = max_sum = 0;

	for (i = 0; i < n; ++i) {
		sum += a[i];

		/* 发现更大的和，更新当前最大值 */
		if (sum > max_sum)
			max_sum = sum;

		/* 如果当前子列和为负，则不能使后面的部分和增大，抛弃 */
		else if (sum < 0)
			sum = 0;
	}

	return max_sum;
}

